蓝桥杯 2025 省 A 红黑树

题目描述

https://www.luogu.com.cn/problem/P12141

思路

容易证明以下两个性质：

每行的前半部分和后半部分对应位颜色相反。
每行的前半部分就是上一行，故答案只与 $k$ 有关，与 $n$ 无关。

每行从 $0$ 开始编号，编号 $x = k - 1$

由 性质 2，答案与 $n$ 无关，不妨设节点在可能的最浅行，那么节点一定在该行的后半部分，不然可以更浅。

考虑 $x$ 的 二进制表示，例如 $x = (101001)_{2}$ ，则由 性质 1，该节点颜色与 $x_{1} = (001001)_{2} = (1001)_{2}$ 对应的节点颜色相反， $x_{1}$ 节点又与 $x_{2} = (0001)_{} = (1)_{2}$ 对应的节点颜色相反， $x_{2}$ 节点又与 $x_{3} = (0)_{2} = 0$ 对应的节点颜色相反，而 $0$ 是根节点，颜色为红色，那么 $x$ 的颜色为黑色。

所以，颜色只和 $x$ 二进制表示中 $1$ 的数量的奇偶性相关，可使用内置函数 __builtin_parity 计算。

代码

#include <iostream>
using namespace std;

int main() {
    int m, k;
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> k >> k;
        cout << (__builtin_parity(k-1) ? "BLACK\n" : "RED\n");
    }
}